package com.leetcode.algorithm.y22.m09.w1;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 1475. 商品折扣后的最终价格
 * 
 * https://leetcode.cn/problems/final-prices-with-a-special-discount-in-a-shop/
 * 
 * @author jie.deng
 *
 */
class Question1475Solution01 {

	public int[] finalPrices(int[] prices) {
		Deque<Integer> stack = new ArrayDeque<>();
		int len = prices.length;
		int[] ans = new int[len];
		for (int i = len - 1; i >= 0; i--) {
			Integer smaller = add2DescStack(prices[i], stack);
			if (smaller == null) {
				ans[i] = prices[i];
			} else {
				ans[i] = prices[i] - smaller.intValue();
			}
		}
		return ans;
	}

	private Integer add2DescStack(int num, Deque<Integer> stack) {
		Integer smaller = null;
		while (!stack.isEmpty() && stack.peekLast().intValue() > num) {
			stack.pollLast();
		}
		if (!stack.isEmpty()) {
			smaller = stack.peekLast();
		}
		stack.offerLast(num);
		return smaller;
	}

}